/*
   @Copyright:LintCode
   @Author:   tjyemail
   @Problem:  http://www.lintcode.com/problem/scramble-string
   @Language: C++
   @Datetime: 20-01-10 17:58
   */

class Solution {
public:
	/**
	 * @param s1: A string
	 * @param s2: Another string
	 * @return: whether s2 is a scrambled string of s1
	 */
	bool isScramble(string &s1, string &s2) {
		// write your code here
		int l1=s1.size(), l2=s2.size();
		if (l1!=l2) return false;
		if (s1==s2) return true;
		unordered_map<char, int> freqs;
		for(const auto &ch:s1)
			++freqs[ch];
		for(const auto &ch:s2)
			if(freqs[ch]--==0) return false;
		for(int len=1; len<l1; ++len){
			string s1l=s1.substr(0, len), s1r=s1.substr(len);
			string s2l=s2.substr(0, len), s2r=s2.substr(len);
			string s2rl=s2.substr(0, l1-len), s2rr=s2.substr(l1-len);
			if ((isScramble(s1l, s2l) && isScramble(s1r, s2r))
					||(isScramble(s1l, s2rr) && isScramble(s1r, s2rl)))
				return true;
		}
		return false;
	}
};
